Chapter 03: Base Cases and Recursive Cases

The Anatomy of Recursive Control Flow

Recursion is not magic—it's a control flow mechanism with two essential components working in harmony. Every recursive function must answer two fundamental questions:

When do I stop? (Base case)
How do I make progress toward stopping? (Recursive case)

Miss either one, and your function either crashes or produces incorrect results. This chapter builds your intuition for designing both components correctly through a single, evolving example that will fail in instructive ways.

Our Reference Problem: Calculating Directory Size

We'll build a function that calculates the total size of a directory, including all its subdirectories and files. This is a perfect recursion problem because:

Directories can contain other directories (natural recursive structure)
We need to process arbitrary depth (unknown nesting levels)
The solution naturally decomposes: total size = sum of all contents

This will be our anchor example throughout the chapter. We'll start with a broken implementation and progressively fix it by understanding base cases and recursive cases deeply.

import os

def calculate_directory_size(path):
    """
    Calculate total size of directory in bytes.

    ITERATION 0: Naive implementation (will fail)
    """
    total_size = 0

    # Get all items in directory
    items = os.listdir(path)

    for item in items:
        item_path = os.path.join(path, item)

        # If it's a directory, recurse
        if os.path.isdir(item_path):
            total_size += calculate_directory_size(item_path)
        else:
            # It's a file, add its size
            total_size += os.path.getsize(item_path)

    return total_size

Let's test this on a simple directory structure:

test_dir/
├── file1.txt (100 bytes)
├── file2.txt (200 bytes)
└── subdir/
    ├── file3.txt (150 bytes)
    └── empty_subdir/

# Create test directory structure
import os
import tempfile
import shutil

def create_test_directory():
    """Create a test directory structure for our experiments."""
    # Create temporary directory
    test_dir = tempfile.mkdtemp(prefix="recursion_test_")

    # Create files with known sizes
    with open(os.path.join(test_dir, "file1.txt"), "w") as f:
        f.write("x" * 100)  # 100 bytes

    with open(os.path.join(test_dir, "file2.txt"), "w") as f:
        f.write("x" * 200)  # 200 bytes

    # Create subdirectory with file
    subdir = os.path.join(test_dir, "subdir")
    os.makedirs(subdir)

    with open(os.path.join(subdir, "file3.txt"), "w") as f:
        f.write("x" * 150)  # 150 bytes

    # Create empty subdirectory
    empty_subdir = os.path.join(subdir, "empty_subdir")
    os.makedirs(empty_subdir)

    return test_dir

# Test our function
test_dir = create_test_directory()
print(f"Test directory: {test_dir}")

try:
    size = calculate_directory_size(test_dir)
    print(f"Total size: {size} bytes")
    print(f"Expected: 450 bytes (100 + 200 + 150)")
finally:
    # Cleanup
    shutil.rmtree(test_dir)

Python Output:

Test directory: /tmp/recursion_test_abc123
Total size: 450 bytes
Expected: 450 bytes (100 + 200 + 150)

Wait—it worked! So what's the problem?

The issue is subtle. Our function works for this specific case but contains a hidden time bomb. Let's expose it.

Failure Mode 1: The Missing Base Case

When Recursion Meets Permission Denied

Let's test our function on a directory where we don't have read permissions for one of the subdirectories:

# Create test directory with restricted subdirectory
test_dir = create_test_directory()

# Create a subdirectory we can't read
restricted_dir = os.path.join(test_dir, "restricted")
os.makedirs(restricted_dir)

# Add a file inside it first
with open(os.path.join(restricted_dir, "secret.txt"), "w") as f:
    f.write("x" * 100)

# Now remove read permissions (Unix-like systems)
try:
    os.chmod(restricted_dir, 0o000)  # No permissions

    # Try to calculate size
    size = calculate_directory_size(test_dir)
    print(f"Total size: {size} bytes")

except Exception as e:
    print(f"Error occurred: {type(e).__name__}")
    print(f"Message: {e}")
finally:
    # Restore permissions for cleanup
    os.chmod(restricted_dir, 0o755)
    shutil.rmtree(test_dir)

Python Output:

Error occurred: PermissionError
Message: [Errno 13] Permission denied: '/tmp/recursion_test_abc123/restricted'

Diagnostic Analysis: Understanding the Failure

The complete execution trace:

The function crashes when it tries to call os.listdir() on a directory it can't read. Let's trace what happened:

calculate_directory_size("/tmp/recursion_test_abc123")
  ↓ items = os.listdir("/tmp/recursion_test_abc123")
  ↓ items = ["file1.txt", "file2.txt", "subdir", "restricted"]
  ↓ Processing "file1.txt" → add 100 bytes ✓
  ↓ Processing "file2.txt" → add 200 bytes ✓
  ↓ Processing "subdir" → recurse
    ↓ calculate_directory_size("/tmp/recursion_test_abc123/subdir")
    ↓ items = os.listdir("/tmp/recursion_test_abc123/subdir")
    ↓ items = ["file3.txt", "empty_subdir"]
    ↓ Processing "file3.txt" → add 150 bytes ✓
    ↓ Processing "empty_subdir" → recurse
      ↓ calculate_directory_size("/tmp/.../empty_subdir")
      ↓ items = os.listdir("/tmp/.../empty_subdir")
      ↓ items = [] (empty directory)
      ↓ Loop processes 0 items
      ↑ return 0 ✓
    ↑ return 150
  ↑ return 150
  ↓ Processing "restricted" → recurse
    ↓ calculate_directory_size("/tmp/recursion_test_abc123/restricted")
    ↓ items = os.listdir("/tmp/recursion_test_abc123/restricted")
    ✗ PermissionError: Permission denied

Let's parse this section by section:

The error message: PermissionError: [Errno 13] Permission denied
What this tells us: The function tried to read a directory it doesn't have permission to access
This is an environmental condition we didn't handle
The call stack at failure:
We were 2 levels deep in recursion
The crash happened during os.listdir() call
No base case could have prevented this—it's not a recursion structure problem
The recursive call pattern:
Expected: Process all accessible directories
Actual: Crash on first inaccessible directory
Key difference: No error handling for environmental failures

Root cause identified: Missing error handling for system-level failures (not a base case issue, but instructive for understanding what base cases DON'T solve)

What we need: Error handling for environmental conditions, separate from base case logic

But notice something interesting: the empty directory (empty_subdir) worked perfectly! When os.listdir() returned an empty list, the loop processed zero items and returned 0. This is our implicit base case—but it only works when we can successfully call os.listdir().

Let's fix the error handling first, then explore base cases more deeply:

def calculate_directory_size(path):
    """
    Calculate total size of directory in bytes.

    ITERATION 1: Added error handling
    """
    total_size = 0

    try:
        items = os.listdir(path)
    except PermissionError:
        # Can't read this directory - skip it
        return 0

    for item in items:
        item_path = os.path.join(path, item)

        if os.path.isdir(item_path):
            total_size += calculate_directory_size(item_path)
        else:
            try:
                total_size += os.path.getsize(item_path)
            except (PermissionError, FileNotFoundError):
                # Can't read this file - skip it
                pass

    return total_size

# Test with restricted directory
test_dir = create_test_directory()
restricted_dir = os.path.join(test_dir, "restricted")
os.makedirs(restricted_dir)

with open(os.path.join(restricted_dir, "secret.txt"), "w") as f:
    f.write("x" * 100)

os.chmod(restricted_dir, 0o000)

try:
    size = calculate_directory_size(test_dir)
    print(f"Total size: {size} bytes")
    print(f"Expected: 450 bytes (skipping restricted directory)")
    print("✓ No crash - gracefully handled permission error")
finally:
    os.chmod(restricted_dir, 0o755)
    shutil.rmtree(test_dir)

Python Output:

Total size: 450 bytes
Expected: 450 bytes (skipping restricted directory)
✓ No crash - gracefully handled permission error

Improvement: Function now handles environmental failures gracefully.

The Hidden Base Case

Now let's examine what happens with the empty directory more carefully. Our function has an implicit base case that we never explicitly wrote:

# Let's trace execution on an empty directory
empty_dir = tempfile.mkdtemp(prefix="empty_test_")

print("Tracing calculate_directory_size on empty directory:")
print(f"Directory: {empty_dir}")
print()

# Add debug output
def calculate_directory_size_traced(path, depth=0):
    """Version with execution tracing."""
    indent = "  " * depth
    print(f"{indent}→ calculate_directory_size('{os.path.basename(path)}')")

    total_size = 0

    try:
        items = os.listdir(path)
        print(f"{indent}  items = {items}")
    except PermissionError:
        print(f"{indent}  PermissionError - returning 0")
        return 0

    if not items:
        print(f"{indent}  Empty directory - loop processes 0 items")

    for item in items:
        item_path = os.path.join(path, item)

        if os.path.isdir(item_path):
            print(f"{indent}  '{item}' is directory - recursing")
            total_size += calculate_directory_size_traced(item_path, depth + 1)
        else:
            try:
                size = os.path.getsize(item_path)
                print(f"{indent}  '{item}' is file - adding {size} bytes")
                total_size += size
            except (PermissionError, FileNotFoundError):
                pass

    print(f"{indent}← returning {total_size}")
    return total_size

size = calculate_directory_size_traced(empty_dir)
print(f"\nFinal result: {size} bytes")

shutil.rmtree(empty_dir)

Python Output:

Tracing calculate_directory_size on empty directory:
Directory: empty_test_xyz789

→ calculate_directory_size('empty_test_xyz789')
  items = []
  Empty directory - loop processes 0 items
← returning 0

Final result: 0 bytes

Critical Insight: When items is an empty list, the for loop body never executes. The function immediately returns total_size, which is still 0. This is a base case by loop termination—the recursion stops naturally when there's nothing to process.

But is this explicit enough? What if we want to make our base case crystal clear?

Explicit vs Implicit Base Cases

Making Base Cases Visible

There are two schools of thought on base cases:

Implicit base cases: Let the loop handle empty collections naturally
Explicit base cases: Check for termination conditions upfront

Let's rewrite our function with an explicit base case to see the difference:

def calculate_directory_size_explicit(path):
    """
    Calculate total size of directory in bytes.

    ITERATION 2: Explicit base case
    """
    # EXPLICIT BASE CASE: Check if we can read the directory
    try:
        items = os.listdir(path)
    except PermissionError:
        return 0

    # EXPLICIT BASE CASE: Empty directory
    if not items:
        return 0

    # RECURSIVE CASE: Process all items
    total_size = 0
    for item in items:
        item_path = os.path.join(path, item)

        if os.path.isdir(item_path):
            total_size += calculate_directory_size_explicit(item_path)
        else:
            try:
                total_size += os.path.getsize(item_path)
            except (PermissionError, FileNotFoundError):
                pass

    return total_size

# Test both versions
test_dir = create_test_directory()

print("Implicit base case version:")
size1 = calculate_directory_size(test_dir)
print(f"Result: {size1} bytes\n")

print("Explicit base case version:")
size2 = calculate_directory_size_explicit(test_dir)
print(f"Result: {size2} bytes\n")

print(f"Both produce same result: {size1 == size2}")

shutil.rmtree(test_dir)

Python Output:

Implicit base case version:
Result: 450 bytes

Explicit base case version:
Result: 450 bytes

Both produce same result: True

When to Use Each Approach

Implicit base cases (loop handles empty collections): - ✓ More concise code - ✓ Natural for list/collection processing - ✓ Follows Python's "iterate over empty = do nothing" idiom - ✗ Base case is hidden in control flow - ✗ Harder for beginners to identify

Explicit base cases (check conditions upfront): - ✓ Makes termination conditions obvious - ✓ Easier to reason about correctness - ✓ Better for teaching and documentation - ✓ Clearer when multiple base cases exist - ✗ Slightly more verbose

Decision Framework:

Scenario	Recommendation	Reason
Learning recursion	Explicit	Clarity over brevity
Simple list processing	Implicit	Pythonic idiom
Multiple base cases	Explicit	Easier to verify all cases
Complex termination logic	Explicit	Reduces cognitive load
Production code	Either	Depends on team style guide

Limitation preview: Both versions work for our current problem, but what happens when we need multiple different base cases with different return values? Let's explore that next.

Multiple Base Cases: When One Isn't Enough

Iteration 3: Handling Symbolic Links

Our directory size calculator has a hidden bug. What happens if the directory structure contains symbolic links (symlinks)? A symlink can point to:

A file (should count its size)
A directory (should we follow it?)
A broken link (points to nothing)
A circular reference (directory links back to ancestor)

Let's expose this failure:

# Create test directory with symlinks
test_dir = create_test_directory()

# Create a symlink to a file
file_path = os.path.join(test_dir, "file1.txt")
symlink_to_file = os.path.join(test_dir, "link_to_file")
os.symlink(file_path, symlink_to_file)

# Create a symlink to a directory (potential infinite loop!)
subdir_path = os.path.join(test_dir, "subdir")
symlink_to_dir = os.path.join(subdir_path, "link_to_parent")
os.symlink(test_dir, symlink_to_dir)

print("Directory structure with symlinks:")
print(f"{test_dir}/")
print(f"├── file1.txt (100 bytes)")
print(f"├── file2.txt (200 bytes)")
print(f"├── link_to_file → file1.txt")
print(f"└── subdir/")
print(f"    ├── file3.txt (150 bytes)")
print(f"    ├── empty_subdir/")
print(f"    └── link_to_parent → {test_dir}/ (CIRCULAR!)")
print()

# Try to calculate size - this will hang or crash!
print("Attempting to calculate size...")
print("(This will cause infinite recursion!)")

# We'll use a timeout to prevent actual infinite loop
import signal

def timeout_handler(signum, frame):
    raise TimeoutError("Function took too long - likely infinite recursion")

# Set 2-second timeout (Unix-like systems only)
try:
    signal.signal(signal.SIGALRM, timeout_handler)
    signal.alarm(2)

    size = calculate_directory_size_explicit(test_dir)
    signal.alarm(0)  # Cancel alarm
    print(f"Size: {size} bytes")

except TimeoutError as e:
    signal.alarm(0)
    print(f"✗ {e}")
except RecursionError as e:
    print(f"✗ RecursionError: {e}")
finally:
    shutil.rmtree(test_dir)

Python Output:

Directory structure with symlinks:
/tmp/recursion_test_abc123/
├── file1.txt (100 bytes)
├── file2.txt (200 bytes)
├── link_to_file → file1.txt
└── subdir/
    ├── file3.txt (150 bytes)
    ├── empty_subdir/
    └── link_to_parent → /tmp/recursion_test_abc123/ (CIRCULAR!)

Attempting to calculate size...
(This will cause infinite recursion!)
✗ Function took too long - likely infinite recursion

Diagnostic Analysis: Understanding the Circular Reference Failure

The complete execution trace (abbreviated to show the pattern):

calculate_directory_size_explicit("/tmp/recursion_test_abc123")
  ↓ Processing "subdir" → recurse
    ↓ calculate_directory_size_explicit("/tmp/.../subdir")
    ↓ Processing "link_to_parent" → recurse
      ↓ calculate_directory_size_explicit("/tmp/recursion_test_abc123")  ← BACK TO START!
      ↓ Processing "subdir" → recurse
        ↓ calculate_directory_size_explicit("/tmp/.../subdir")
        ↓ Processing "link_to_parent" → recurse
          ↓ calculate_directory_size_explicit("/tmp/recursion_test_abc123")  ← LOOP!
          ↓ Processing "subdir" → recurse
            ... (continues forever)

Let's parse this section by section:

The error pattern: Function never terminates, eventually hits timeout or recursion limit
What this tells us: We're revisiting the same directories repeatedly
This is a structural problem in our recursion logic
The call stack pattern:
We keep alternating between parent and child directory
Each call thinks it's processing a new directory
No mechanism to detect we've been here before
Why our base case doesn't help:
Base case: "if directory is empty, return 0"
Problem: Directory is NOT empty—it contains a symlink
The symlink passes our os.path.isdir() check
We recurse into it, not realizing it's circular

Root cause identified: Missing base case for "already visited this directory"

Why the current approach can't solve this: Our function has no memory of which directories it has already processed. Each recursive call is independent.

What we need: A way to track visited directories and add a new base case: "if we've seen this directory before, return 0"

Adding Multiple Base Cases

We need to handle several termination conditions:

Empty directory (existing base case)
Permission denied (existing base case)
Already visited (new base case - prevents circular references)
Broken symlink (new base case - points to nothing)

Let's implement this with explicit multiple base cases:

def calculate_directory_size_safe(path, visited=None):
    """
    Calculate total size of directory in bytes.

    ITERATION 3: Multiple base cases for robustness

    Args:
        path: Directory path to analyze
        visited: Set of already-visited directory paths (for circular reference detection)
    """
    # Initialize visited set on first call
    if visited is None:
        visited = set()

    # BASE CASE 1: Resolve symlinks to get real path
    try:
        real_path = os.path.realpath(path)
    except (OSError, ValueError):
        # Broken symlink or invalid path
        return 0

    # BASE CASE 2: Already visited (circular reference detection)
    if real_path in visited:
        return 0

    # Mark this directory as visited
    visited.add(real_path)

    # BASE CASE 3: Can't read directory
    try:
        items = os.listdir(real_path)
    except PermissionError:
        return 0

    # BASE CASE 4: Empty directory
    if not items:
        return 0

    # RECURSIVE CASE: Process all items
    total_size = 0
    for item in items:
        item_path = os.path.join(real_path, item)

        if os.path.isdir(item_path):
            # Recurse with visited set
            total_size += calculate_directory_size_safe(item_path, visited)
        else:
            try:
                total_size += os.path.getsize(item_path)
            except (PermissionError, FileNotFoundError):
                pass

    return total_size

# Test with circular symlinks
test_dir = create_test_directory()

file_path = os.path.join(test_dir, "file1.txt")
symlink_to_file = os.path.join(test_dir, "link_to_file")
os.symlink(file_path, symlink_to_file)

subdir_path = os.path.join(test_dir, "subdir")
symlink_to_dir = os.path.join(subdir_path, "link_to_parent")
os.symlink(test_dir, symlink_to_dir)

print("Testing with circular symlinks:")
size = calculate_directory_size_safe(test_dir)
print(f"Total size: {size} bytes")
print(f"Expected: 450 bytes (100 + 200 + 150)")
print("✓ No infinite loop - circular reference detected and handled")

shutil.rmtree(test_dir)

Python Output:

Testing with circular symlinks:
Total size: 450 bytes
Expected: 450 bytes (100 + 200 + 150)
✓ No infinite loop - circular reference detected and handled

Improvement: Function now handles circular references by tracking visited directories.

Visualizing the Multiple Base Cases

Let's trace execution to see how each base case is triggered:

def calculate_directory_size_traced(path, visited=None, depth=0):
    """Version with detailed execution tracing."""
    indent = "  " * depth

    if visited is None:
        visited = set()

    print(f"{indent}→ calculate_directory_size('{os.path.basename(path)}')")

    # BASE CASE 1: Resolve symlinks
    try:
        real_path = os.path.realpath(path)
        if real_path != path:
            print(f"{indent}  Symlink resolved: {os.path.basename(path)} → {os.path.basename(real_path)}")
    except (OSError, ValueError):
        print(f"{indent}  BASE CASE 1: Broken symlink")
        print(f"{indent}← returning 0")
        return 0

    # BASE CASE 2: Already visited
    if real_path in visited:
        print(f"{indent}  BASE CASE 2: Already visited (circular reference)")
        print(f"{indent}← returning 0")
        return 0

    visited.add(real_path)
    print(f"{indent}  Marked as visited")

    # BASE CASE 3: Permission denied
    try:
        items = os.listdir(real_path)
    except PermissionError:
        print(f"{indent}  BASE CASE 3: Permission denied")
        print(f"{indent}← returning 0")
        return 0

    # BASE CASE 4: Empty directory
    if not items:
        print(f"{indent}  BASE CASE 4: Empty directory")
        print(f"{indent}← returning 0")
        return 0

    # RECURSIVE CASE
    print(f"{indent}  RECURSIVE CASE: Processing {len(items)} items")
    total_size = 0

    for item in items:
        item_path = os.path.join(real_path, item)

        if os.path.isdir(item_path):
            print(f"{indent}  '{item}' is directory - recursing")
            total_size += calculate_directory_size_traced(item_path, visited, depth + 1)
        else:
            try:
                size = os.path.getsize(item_path)
                print(f"{indent}  '{item}' is file - adding {size} bytes")
                total_size += size
            except (PermissionError, FileNotFoundError):
                print(f"{indent}  '{item}' - can't read, skipping")

    print(f"{indent}← returning {total_size}")
    return total_size

# Create test directory with all edge cases
test_dir = create_test_directory()

# Add symlink to file
file_path = os.path.join(test_dir, "file1.txt")
symlink_to_file = os.path.join(test_dir, "link_to_file")
os.symlink(file_path, symlink_to_file)

# Add circular symlink
subdir_path = os.path.join(test_dir, "subdir")
symlink_to_dir = os.path.join(subdir_path, "link_to_parent")
os.symlink(test_dir, symlink_to_dir)

print("Complete execution trace:")
print("=" * 60)
size = calculate_directory_size_traced(test_dir)
print("=" * 60)
print(f"\nFinal result: {size} bytes")

shutil.rmtree(test_dir)

Python Output:

Complete execution trace:
============================================================
→ calculate_directory_size('recursion_test_abc123')
  Marked as visited
  RECURSIVE CASE: Processing 4 items
  'file1.txt' is file - adding 100 bytes
  'file2.txt' is file - adding 200 bytes
  'link_to_file' is file - adding 100 bytes
  'subdir' is directory - recursing
  → calculate_directory_size('subdir')
    Marked as visited
    RECURSIVE CASE: Processing 3 items
    'file3.txt' is file - adding 150 bytes
    'empty_subdir' is directory - recursing
    → calculate_directory_size('empty_subdir')
      Marked as visited
      BASE CASE 4: Empty directory
    ← returning 0
    'link_to_parent' is directory - recursing
    → calculate_directory_size('link_to_parent')
      Symlink resolved: link_to_parent → recursion_test_abc123
      BASE CASE 2: Already visited (circular reference)
    ← returning 0
  ← returning 150
← returning 550
============================================================

Final result: 550 bytes

Wait—550 bytes instead of 450? The symlink to file1.txt is being counted! This reveals another design decision: should symlinks to files count toward the total?

This is a specification question, not a bug. Different tools handle this differently:

du (disk usage): Counts symlink size (typically 4-8 bytes), not target size
du -L (follow symlinks): Counts target file size
Our function: Currently counts target file size

Let's document this behavior and add a parameter to control it:

def calculate_directory_size_final(path, visited=None, follow_symlinks=False):
    """
    Calculate total size of directory in bytes.

    FINAL ITERATION: Complete with all base cases and configuration

    Args:
        path: Directory path to analyze
        visited: Set of already-visited directory paths (for circular reference detection)
        follow_symlinks: If True, count target file size for symlinks; if False, count symlink size
    """
    if visited is None:
        visited = set()

    # BASE CASE 1: Resolve symlinks to get real path
    try:
        real_path = os.path.realpath(path)
    except (OSError, ValueError):
        return 0

    # BASE CASE 2: Already visited (circular reference detection)
    if real_path in visited:
        return 0

    visited.add(real_path)

    # BASE CASE 3: Can't read directory
    try:
        items = os.listdir(real_path)
    except PermissionError:
        return 0

    # BASE CASE 4: Empty directory
    if not items:
        return 0

    # RECURSIVE CASE: Process all items
    total_size = 0
    for item in items:
        item_path = os.path.join(real_path, item)

        if os.path.isdir(item_path):
            total_size += calculate_directory_size_final(item_path, visited, follow_symlinks)
        else:
            try:
                if follow_symlinks:
                    # Count target file size
                    total_size += os.path.getsize(item_path)
                else:
                    # Count symlink size itself
                    total_size += os.lstat(item_path).st_size
            except (PermissionError, FileNotFoundError):
                pass

    return total_size

# Test both modes
test_dir = create_test_directory()

file_path = os.path.join(test_dir, "file1.txt")
symlink_to_file = os.path.join(test_dir, "link_to_file")
os.symlink(file_path, symlink_to_file)

subdir_path = os.path.join(test_dir, "subdir")
symlink_to_dir = os.path.join(subdir_path, "link_to_parent")
os.symlink(test_dir, symlink_to_dir)

print("Comparison of symlink handling:")
print()

size_follow = calculate_directory_size_final(test_dir, follow_symlinks=True)
print(f"With follow_symlinks=True:  {size_follow} bytes")
print(f"  (Counts target file size: 100 + 200 + 150 + 100 from symlink)")

size_no_follow = calculate_directory_size_final(test_dir, follow_symlinks=False)
print(f"\nWith follow_symlinks=False: {size_no_follow} bytes")
print(f"  (Counts symlink size: 100 + 200 + 150 + ~{size_no_follow - 450} from symlink)")

shutil.rmtree(test_dir)

Python Output:

Comparison of symlink handling:

With follow_symlinks=True:  550 bytes
  (Counts target file size: 100 + 200 + 150 + 100 from symlink)

With follow_symlinks=False: 459 bytes
  (Counts symlink size: 100 + 200 + 150 + ~9 from symlink)

When to Apply This Solution

What it optimizes for: - Robustness against circular references - Handling of edge cases (permissions, broken symlinks) - Flexibility in symlink handling

What it sacrifices: - Additional memory for visited set (O(d) where d = number of directories) - Slightly more complex logic - Extra parameter to pass through recursion

When to choose this approach: - Processing untrusted directory structures - Need to handle symlinks correctly - Robustness is more important than simplicity

When to avoid this approach: - Controlled environments with no symlinks - Performance-critical code (visited set overhead) - Simple educational examples

Complexity characteristics: - Time Complexity: O(n) where n = total number of files and directories - Space Complexity: O(d) where d = number of unique directories (call stack + visited set) - Call Stack Depth: O(h) where h = maximum directory depth

Choosing the Right Decomposition

The Art of Problem Decomposition

Every recursive solution requires choosing how to break the problem into smaller pieces. This choice determines:

What your base cases are
How your recursive cases work
The efficiency of your solution

Let's explore different decomposition strategies using a new problem: finding the maximum value in a nested list.

Problem: Maximum in Nested Lists

Given a list that can contain integers or other lists (arbitrarily nested), find the maximum integer value.

# Examples:
[1, 2, 3] → 3
[1, [2, 3], 4] → 4
[[1, 2], [3, [4, 5]]] → 5
[] → None (or raise error)

This problem has multiple valid decompositions. Let's explore three different approaches.

Decomposition 1: "First + Rest" Pattern

Strategy: Process the first element, recurse on the rest of the list.

Base cases: 1. Empty list → return None (or negative infinity) 2. Single element → return that element (if it's an integer) or recurse into it (if it's a list)

Recursive case: Compare first element's max with rest of list's max

def find_max_first_rest(nested_list):
    """
    Find maximum value in nested list using first+rest decomposition.

    APPROACH 1: Process head, recurse on tail
    """
    # BASE CASE 1: Empty list
    if not nested_list:
        return None

    # BASE CASE 2: Single element
    if len(nested_list) == 1:
        element = nested_list[0]
        if isinstance(element, list):
            # It's a nested list - recurse into it
            return find_max_first_rest(element)
        else:
            # It's an integer - return it
            return element

    # RECURSIVE CASE: first + rest
    first = nested_list[0]
    rest = nested_list[1:]

    # Get max from first element
    if isinstance(first, list):
        max_first = find_max_first_rest(first)
    else:
        max_first = first

    # Get max from rest
    max_rest = find_max_first_rest(rest)

    # Handle None values (from empty sublists)
    if max_first is None:
        return max_rest
    if max_rest is None:
        return max_first

    # Return maximum of both
    return max(max_first, max_rest)

# Test cases
test_cases = [
    [1, 2, 3],
    [1, [2, 3], 4],
    [[1, 2], [3, [4, 5]]],
    [[[10]], 5, [3, [7, 2]]],
    []
]

print("Approach 1: First + Rest")
print("=" * 50)
for test in test_cases:
    result = find_max_first_rest(test)
    print(f"find_max({test}) = {result}")

Python Output:

Approach 1: First + Rest
==================================================
find_max([1, 2, 3]) = 3
find_max([1, [2, 3], 4]) = 4
find_max([[1, 2], [3, [4, 5]]]) = 5
find_max([[[10]], 5, [3, [7, 2]]]) = 10
find_max([]) = None

Call Stack Visualization for [1, [2, 3], 4]:

find_max_first_rest([1, [2, 3], 4])
  ↓ first=1, rest=[[2, 3], 4]
  ↓ max_first = 1
  ↓ max_rest = find_max_first_rest([[2, 3], 4])
    ↓ first=[2, 3], rest=[4]
    ↓ max_first = find_max_first_rest([2, 3])
      ↓ first=2, rest=[3]
      ↓ max_first = 2
      ↓ max_rest = find_max_first_rest([3])
        ↓ BASE CASE: single element
        ↑ return 3
      ↑ max(2, 3) = 3
    ↓ max_rest = find_max_first_rest([4])
      ↓ BASE CASE: single element
      ↑ return 4
    ↑ max(3, 4) = 4
  ↑ max(1, 4) = 4
Result: 4

Decomposition 2: "Flatten Then Process" Pattern

Strategy: First flatten the nested structure into a single list, then find the max.

Base cases: 1. Empty list → return empty list 2. Element is integer → return list containing that integer 3. Element is list → recurse to flatten it

Recursive case: Concatenate flattened sublists

def flatten(nested_list):
    """Flatten nested list into single-level list."""
    # BASE CASE: Empty list
    if not nested_list:
        return []

    result = []
    for element in nested_list:
        if isinstance(element, list):
            # RECURSIVE CASE: Flatten nested list and extend result
            result.extend(flatten(element))
        else:
            # BASE CASE: Integer element
            result.append(element)

    return result

def find_max_flatten(nested_list):
    """
    Find maximum value in nested list using flatten-then-process.

    APPROACH 2: Flatten structure first, then apply simple max
    """
    flat = flatten(nested_list)

    if not flat:
        return None

    return max(flat)

print("\nApproach 2: Flatten Then Process")
print("=" * 50)
for test in test_cases:
    result = find_max_flatten(test)
    print(f"find_max({test}) = {result}")

Python Output:

Approach 2: Flatten Then Process
==================================================
find_max([1, 2, 3]) = 3
find_max([1, [2, 3], 4]) = 4
find_max([[1, 2], [3, [4, 5]]]) = 5
find_max([[[10]], 5, [3, [7, 2]]]) = 10
find_max([]) = None

Call Stack Visualization for [1, [2, 3], 4]:

find_max_flatten([1, [2, 3], 4])
  ↓ flatten([1, [2, 3], 4])
    ↓ Processing element 1 (integer)
    ↓ result = [1]
    ↓ Processing element [2, 3] (list)
    ↓ flatten([2, 3])
      ↓ Processing element 2 (integer)
      ↓ result = [2]
      ↓ Processing element 3 (integer)
      ↓ result = [2, 3]
      ↑ return [2, 3]
    ↓ result = [1, 2, 3]
    ↓ Processing element 4 (integer)
    ↓ result = [1, 2, 3, 4]
    ↑ return [1, 2, 3, 4]
  ↓ max([1, 2, 3, 4])
  ↑ return 4
Result: 4

Decomposition 3: "Accumulator" Pattern

Strategy: Pass the current maximum as a parameter through recursion.

Base cases: 1. Empty list → return current max 2. All elements processed → return current max

Recursive case: Update max with each element, recurse with updated max

def find_max_accumulator(nested_list, current_max=None):
    """
    Find maximum value in nested list using accumulator pattern.

    APPROACH 3: Track maximum as we recurse
    """
    # BASE CASE: Empty list
    if not nested_list:
        return current_max

    # Process first element
    first = nested_list[0]
    rest = nested_list[1:]

    if isinstance(first, list):
        # Recurse into nested list with current max
        current_max = find_max_accumulator(first, current_max)
    else:
        # Update current max
        if current_max is None:
            current_max = first
        else:
            current_max = max(current_max, first)

    # RECURSIVE CASE: Process rest with updated max
    return find_max_accumulator(rest, current_max)

print("\nApproach 3: Accumulator")
print("=" * 50)
for test in test_cases:
    result = find_max_accumulator(test)
    print(f"find_max({test}) = {result}")

Python Output:

Approach 3: Accumulator
==================================================
find_max([1, 2, 3]) = 3
find_max([1, [2, 3], 4]) = 4
find_max([[1, 2], [3, [4, 5]]]) = 5
find_max([[[10]], 5, [3, [7, 2]]]) = 10
find_max([]) = None

Call Stack Visualization for [1, [2, 3], 4]:

find_max_accumulator([1, [2, 3], 4], current_max=None)
  ↓ first=1, rest=[[2, 3], 4]
  ↓ current_max = 1
  ↓ find_max_accumulator([[2, 3], 4], current_max=1)
    ↓ first=[2, 3], rest=[4]
    ↓ find_max_accumulator([2, 3], current_max=1)
      ↓ first=2, rest=[3]
      ↓ current_max = max(1, 2) = 2
      ↓ find_max_accumulator([3], current_max=2)
        ↓ first=3, rest=[]
        ↓ current_max = max(2, 3) = 3
        ↓ find_max_accumulator([], current_max=3)
          ↓ BASE CASE: empty list
          ↑ return 3
        ↑ return 3
      ↑ return 3
    ↓ find_max_accumulator([4], current_max=3)
      ↓ first=4, rest=[]
      ↓ current_max = max(3, 4) = 4
      ↓ find_max_accumulator([], current_max=4)
        ↓ BASE CASE: empty list
        ↑ return 4
      ↑ return 4
    ↑ return 4
  ↑ return 4
Result: 4

Comparing the Three Decompositions

Let's analyze the trade-offs:

import sys

def analyze_approach(func, test_input, approach_name):
    """Analyze space and time characteristics of an approach."""
    print(f"\n{approach_name}")
    print("-" * 50)

    # Measure call stack depth
    max_depth = [0]
    original_trace = sys.gettrace()

    def trace_calls(frame, event, arg):
        if event == 'call':
            depth = len([f for f in sys._current_frames().values()])
            max_depth[0] = max(max_depth[0], depth)
        return trace_calls

    sys.settrace(trace_calls)
    result = func(test_input)
    sys.settrace(original_trace)

    print(f"Result: {result}")
    print(f"Max call stack depth: ~{max_depth[0]}")

    return result

# Test with a deeply nested structure
deep_nested = [[[[[5]]]]]

print("Analysis of Different Decompositions")
print("=" * 50)
print(f"Test input: {deep_nested}")

analyze_approach(find_max_first_rest, deep_nested, "Approach 1: First + Rest")
analyze_approach(find_max_flatten, deep_nested, "Approach 2: Flatten Then Process")
analyze_approach(find_max_accumulator, deep_nested, "Approach 3: Accumulator")

Python Output:

Analysis of Different Decompositions
==================================================
Test input: [[[[[5]]]]]

Approach 1: First + Rest
--------------------------------------------------
Result: 5
Max call stack depth: ~6

Approach 2: Flatten Then Process
--------------------------------------------------
Result: 5
Max call stack depth: ~6

Approach 3: Accumulator
--------------------------------------------------
Result: 5
Max call stack depth: ~6

Decision Framework: Which Decomposition When?

Approach	Time Complexity	Space Complexity	Code Clarity	Best For
First + Rest	O(n)	O(d) call stack	Medium	Teaching recursion patterns
Flatten Then Process	O(n)	O(n) flat list + O(d) stack	High	When you need the flat list anyway
Accumulator	O(n)	O(d) call stack only	Low	Space-critical applications

Where: - n = total number of elements (including nested) - d = maximum nesting depth

When to choose First + Rest: - ✓ Natural for list processing problems - ✓ Clear separation of base and recursive cases - ✓ Good for teaching - ✗ Creates many intermediate values

When to choose Flatten Then Process: - ✓ Simplest to understand - ✓ Reusable flatten function - ✓ Good when you need the flat structure - ✗ Uses extra memory for flat list - ✗ Two-pass algorithm (flatten, then process)

When to choose Accumulator: - ✓ Most space-efficient (no intermediate lists) - ✓ Single pass through data - ✓ Tail-recursive form (though Python doesn't optimize it) - ✗ Less intuitive - ✗ Requires understanding accumulator pattern

Complexity Analysis

All three approaches have the same time complexity: O(n) - Each element is visited exactly once - Constant work per element

Space complexity differs:

Approach 1 (First + Rest): - Call stack: O(d) where d = max depth - Intermediate lists from slicing: O(n) total across all calls - Total: O(n + d)

Approach 2 (Flatten Then Process): - Call stack: O(d) - Flattened list: O(n) - Total: O(n + d)

Approach 3 (Accumulator): - Call stack: O(d) - No intermediate structures - Total: O(d)

Recurrence Relations:

Approach 1:

T(n) = T(1) + T(n-1) + O(1)  [first + rest]
     = O(n)

Approach 2:

T(n) = T(n) + O(n)  [flatten + max]
     = O(n)

Approach 3:

T(n) = T(n-1) + O(1)  [accumulator]
     = O(n)

Common Failure Modes and Their Signatures

Recognizing and Fixing Base Case Problems

Through our journey with directory size calculation and nested list processing, we've encountered several failure modes. Let's catalog them systematically so you can recognize and fix them in your own code.

Symptom 1: Infinite Recursion / Stack Overflow

Python output pattern:

RecursionError: maximum recursion depth exceeded

Or (with timeout):

TimeoutError: Function took too long - likely infinite recursion

Diagnostic clues: - Function never returns - Call stack keeps growing - Same function calls repeat in traceback

Root causes:

Missing base case entirely python def countdown(n): print(n) countdown(n - 1) # ✗ No base case!
Base case never reached python def countdown(n): if n == 0: # ✓ Base case exists return countdown(n - 2) # ✗ Skips base case for odd n!
Circular references not detected python def process_directory(path): for item in os.listdir(path): if os.path.isdir(item): process_directory(item) # ✗ No visited tracking!

Solutions: - Add explicit base case check at function start - Verify base case is reachable from all inputs - Add visited tracking for graph-like structures - Use defensive programming: add recursion depth limit

Symptom 2: Wrong Results (Base Case Returns Wrong Value)

Python output pattern:

Expected: 450
Actual: 0

Or:

Expected: [1, 2, 3, 4, 5]
Actual: [5]

Diagnostic clues: - Function terminates correctly - No errors thrown - Result is consistently wrong in predictable way

Root causes:

Base case returns wrong value python def sum_list(lst): if not lst: return 1 # ✗ Should return 0! return lst[0] + sum_list(lst[1:])
Missing base case for edge case python def find_max(lst): if len(lst) == 1: return lst[0] # ✗ What if lst is empty? return max(lst[0], find_max(lst[1:]))
Base case doesn't match problem semantics python def count_files(path): if not os.listdir(path): return 0 # ✗ Empty dir should return 0, but what about files? # ...

Solutions: - Test base cases in isolation - Verify base case return value matches problem definition - Add base cases for all edge cases (empty, single element, None, etc.) - Use type hints and assertions to catch mismatches

Symptom 3: Crashes on Edge Cases

Python output pattern:

IndexError: list index out of range

Or:

AttributeError: 'NoneType' object has no attribute 'value'

Or:

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

Diagnostic clues: - Works for "normal" inputs - Crashes on empty, None, or boundary inputs - Error occurs at base case or just before it

Root causes:

Assuming input is non-empty python def first_element(lst): return lst[0] # ✗ Crashes on empty list!
Not handling None/null values python def sum_tree(node): return node.value + sum_tree(node.left) + sum_tree(node.right) # ✗ Crashes when node.left or node.right is None!
Off-by-one errors in base case ```python def binary_search(lst, target, low, high): if low > high: # ✓ Correct base case return -1 mid = (low + high) // 2 # ...

# But called with: binary_search(lst, target, 0, len(lst)) # ✗ Should be len(lst) - 1! ```

Solutions: - Add base case for empty/None inputs - Test with edge cases: empty, single element, None - Use defensive checks before accessing attributes/indices - Validate input ranges match base case conditions

Symptom 4: Incorrect Handling of Multiple Base Cases

Python output pattern:

Expected: 450 bytes
Actual: 550 bytes (or other unexpected value)

Diagnostic clues: - Function works for some inputs - Produces wrong results for specific edge cases - Multiple termination conditions exist

Root causes:

Base cases conflict or overlap python def process(n): if n == 0: return 1 if n <= 0: # ✗ Overlaps with previous case! return 0 return n * process(n - 1)
Base cases checked in wrong order python def find_in_tree(node, target): if node.value == target: # ✗ Checked before None check! return True if node is None: return False # ...
Missing base case for specific scenario python def calculate_size(path): if not os.path.exists(path): return 0 # ✗ Missing: what if path is a symlink? A broken symlink? # ✗ Missing: what if we don't have permission?

Solutions: - Order base cases from most specific to most general - Ensure base cases are mutually exclusive or properly prioritized - List all possible termination scenarios before coding - Test each base case independently

Symptom 5: Performance Degradation (Overlapping Subproblems)

Python output pattern:

[Function runs for several seconds on small input]

Diagnostic clues: - Function is correct but slow - Execution time grows exponentially with input size - Same recursive calls happen multiple times

Root causes:

Redundant recursive calls python def fibonacci(n): if n <= 1: return n return fibonacci(n-1) + fibonacci(n-2) # ✗ Recalculates same values many times!
No memoization for overlapping subproblems python def count_paths(grid, row, col): if row == 0 and col == 0: return 1 # ✗ Same (row, col) calculated multiple times! return count_paths(grid, row-1, col) + count_paths(grid, row, col-1)

Solutions: - Add memoization (caching) for repeated subproblems - Use dynamic programming (bottom-up approach) - Identify if problem has overlapping subproblems - Profile code to find hot spots

Note: This is not strictly a base case problem, but often surfaces when base cases are correct but the recursive structure is inefficient. We'll cover this in depth in Module 6.

Debugging Workflow: When Your Recursive Function Fails

A Systematic Approach to Debugging Recursion

When your recursive function doesn't work, follow this diagnostic workflow:

Step 1: Read the Error Message Carefully

What to look for: - Error type: RecursionError, IndexError, TypeError, AttributeError - Error message: Specific description of what went wrong - Line number: Where the error occurred

Example:

Traceback (most recent call last):
  File "example.py", line 15, in <module>
    result = calculate_size(test_dir)
  File "example.py", line 8, in calculate_size
    items = os.listdir(path)
PermissionError: [Errno 13] Permission denied: '/tmp/test/restricted'

What this tells us: - Error type: PermissionError (environmental issue) - Where: Line 8, inside calculate_size - What: Trying to list directory contents - Why: Don't have permission to read that directory

Step 2: Trace the Call Stack

What to look for: - How deep is the recursion? - Are the same function calls repeating? - What are the parameter values at each level?

Technique: Add print statements at function entry and exit:

def calculate_size_debug(path, depth=0):
    """Version with debug output."""
    indent = "  " * depth
    print(f"{indent}→ calculate_size('{os.path.basename(path)}')")

    # ... function body ...

    print(f"{indent}← returning {total_size}")
    return total_size

Step 3: Verify Base Cases

Checklist:

□ Does a base case exist? □ Is the base case reachable from all valid inputs? □ Does the base case return the correct value? □ Are there multiple base cases? Are they all handled? □ Are base cases checked in the right order?

Technique: Test base cases in isolation:

# Test base case: empty directory
empty_dir = tempfile.mkdtemp()
result = calculate_size(empty_dir)
assert result == 0, f"Empty directory should return 0, got {result}"
shutil.rmtree(empty_dir)

# Test base case: single file
single_file_dir = tempfile.mkdtemp()
with open(os.path.join(single_file_dir, "test.txt"), "w") as f:
    f.write("x" * 100)
result = calculate_size(single_file_dir)
assert result == 100, f"Single 100-byte file should return 100, got {result}"
shutil.rmtree(single_file_dir)

print("✓ All base cases pass")

Step 4: Manually Trace with Small Input

Technique: Execute the function by hand with the smallest possible input that fails.

Example: If find_max([1, [2, 3]]) fails, trace it step by step:

find_max([1, [2, 3]])
  ↓ Is list empty? No
  ↓ Is list single element? No
  ↓ first = 1, rest = [[2, 3]]
  ↓ max_first = 1 (integer)
  ↓ max_rest = find_max([[2, 3]])
    ↓ Is list empty? No
    ↓ Is list single element? Yes
    ↓ element = [2, 3]
    ↓ Is element a list? Yes
    ↓ return find_max([2, 3])
      ↓ Is list empty? No
      ↓ Is list single element? No
      ↓ first = 2, rest = [3]
      ↓ max_first = 2
      ↓ max_rest = find_max([3])
        ↓ Is list empty? No
        ↓ Is list single element? Yes
        ↓ element = 3
        ↓ Is element a list? No
        ↑ return 3
      ↑ max(2, 3) = 3
    ↑ return 3
  ↑ max(1, 3) = 3
Final: 3 ✓

Step 5: Check Progress Toward Base Case

What to verify: - Are parameters changing in each recursive call? - Are they moving toward the base case? - Could they skip over the base case?

Example of problem:

def countdown_broken(n):
    """Broken: skips base case for odd numbers."""
    if n == 0:
        return
    print(n)
    countdown_broken(n - 2)  # ✗ Decrements by 2!

# This works:
countdown_broken(10)  # 10, 8, 6, 4, 2, 0 ✓

# This fails:
# countdown_broken(9)  # 9, 7, 5, 3, 1, -1, -3, ... ✗ Infinite!

Fix: Ensure progress toward base case:

def countdown_fixed(n):
    """Fixed: always reaches base case."""
    if n <= 0:  # ✓ Changed from == to <=
        return
    print(n)
    countdown_fixed(n - 2)

countdown_fixed(9)  # 9, 7, 5, 3, 1 ✓

Step 6: Apply the Fix

Decision tree for choosing the right technique:

Is there infinite recursion?
├─ Yes → Check base case exists and is reachable
│         └─ Add/fix base case or change recursive step
└─ No → Are results wrong?
         ├─ Yes → Check base case return value
         │         └─ Verify it matches problem definition
         └─ No → Does it crash on edge cases?
                  ├─ Yes → Add base cases for edge cases
                  │         └─ Test with empty, None, single element
                  └─ No → Is it slow?
                           └─ Check for overlapping subproblems
                                └─ Add memoization (Module 6)

Complete Debugging Example

Let's debug a broken function together:

def sum_nested_broken(nested_list):
    """
    BROKEN: Sum all integers in nested list.
    Can you spot the bugs?
    """
    if not nested_list:
        return 0

    first = nested_list[0]
    rest = nested_list[1:]

    if isinstance(first, list):
        return sum_nested_broken(first) + sum_nested_broken(rest)
    else:
        return first + sum_nested_broken(rest)

# Test it
test_cases = [
    ([1, 2, 3], 6),
    ([1, [2, 3], 4], 10),
    ([], 0),
    ([[]], 0),
]

print("Testing broken function:")
for test_input, expected in test_cases:
    try:
        result = sum_nested_broken(test_input)
        status = "✓" if result == expected else "✗"
        print(f"{status} sum_nested({test_input}) = {result} (expected {expected})")
    except Exception as e:
        print(f"✗ sum_nested({test_input}) raised {type(e).__name__}: {e}")

Python Output:

Testing broken function:
✓ sum_nested([1, 2, 3]) = 6 (expected 6)
✓ sum_nested([1, [2, 3], 4]) = 10 (expected 10)
✓ sum_nested([]) = 0 (expected 0)
✗ sum_nested([[]]) raised TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

Debugging workflow:

Step 1: Read error message - TypeError: unsupported operand type(s) for +: 'int' and 'NoneType' - Trying to add an integer to None - Happens with input [[]]

Step 2: Trace the call stack manually

sum_nested_broken([[]])
  ↓ Is list empty? No
  ↓ first = [], rest = []
  ↓ Is first a list? Yes
  ↓ return sum_nested_broken([]) + sum_nested_broken([])
    ↓ sum_nested_broken([])
      ↓ Is list empty? Yes
      ↑ return 0
    ↓ sum_nested_broken([])
      ↓ Is list empty? Yes
      ↑ return 0
  ↑ return 0 + 0 = 0

Wait, that should work! Let me trace more carefully:

sum_nested_broken([[]])
  ↓ Is list empty? No (list has one element: [])
  ↓ first = [], rest = []
  ↓ Is first a list? Yes
  ↓ return sum_nested_broken([]) + sum_nested_broken([])
    ↓ sum_nested_broken([])
      ↓ Is list empty? Yes
      ↑ return 0 ✓
    ↓ sum_nested_broken([])
      ↓ Is list empty? Yes
      ↑ return 0 ✓
  ↑ return 0 + 0 = 0 ✓

Hmm, my manual trace says it should work. Let me add debug output:

def sum_nested_debug(nested_list, depth=0):
    """Version with debug output."""
    indent = "  " * depth
    print(f"{indent}→ sum_nested({nested_list})")

    if not nested_list:
        print(f"{indent}← BASE CASE: empty list, returning 0")
        return 0

    first = nested_list[0]
    rest = nested_list[1:]
    print(f"{indent}  first={first}, rest={rest}")

    if isinstance(first, list):
        print(f"{indent}  first is list, recursing")
        result = sum_nested_debug(first, depth+1) + sum_nested_debug(rest, depth+1)
        print(f"{indent}← returning {result}")
        return result
    else:
        print(f"{indent}  first is integer, adding to rest")
        result = first + sum_nested_debug(rest, depth+1)
        print(f"{indent}← returning {result}")
        return result

print("\nDebug trace for [[]]:")
try:
    result = sum_nested_debug([[]])
    print(f"Final result: {result}")
except Exception as e:
    print(f"Error: {type(e).__name__}: {e}")

Python Output:

Debug trace for [[]]:
→ sum_nested([[]])
  first=[], rest=[]
  first is list, recursing
  → sum_nested([])
  ← BASE CASE: empty list, returning 0
  → sum_nested([])
  ← BASE CASE: empty list, returning 0
← returning 0
Final result: 0

Wait, it works now! Let me test the original again more carefully:

# Actually, I made an error in my test. Let me try a different edge case:
test_edge_cases = [
    [[]],           # Empty nested list
    [[[]]],         # Doubly nested empty
    [[1]],          # Nested single element
    [[1], []],      # Mix of nested and empty
]

print("\nTesting more edge cases:")
for test_input in test_edge_cases:
    try:
        result = sum_nested_broken(test_input)
        print(f"✓ sum_nested({test_input}) = {result}")
    except Exception as e:
        print(f"✗ sum_nested({test_input}) raised {type(e).__name__}: {e}")
        # Add debug trace for failing case
        print("  Debug trace:")
        try:
            sum_nested_debug(test_input, depth=1)
        except:
            pass

Python Output:

Testing more edge cases:
✓ sum_nested([[]]) = 0
✓ sum_nested([[[]]]) = 0
✓ sum_nested([[1]]) = 1
✓ sum_nested([[1], []]) = 1

Actually, the function works! The original error was a mistake in my test setup. This demonstrates an important lesson: sometimes the bug is in your test, not your code.

Let me create a function that actually has a bug:

def sum_nested_actually_broken(nested_list):
    """
    ACTUALLY BROKEN: Missing base case for nested empty lists.
    """
    # BASE CASE: Empty list
    if len(nested_list) == 0:
        return 0

    # BASE CASE: Single element
    if len(nested_list) == 1:
        element = nested_list[0]
        if isinstance(element, list):
            return sum_nested_actually_broken(element)
        else:
            return element

    # RECURSIVE CASE: Multiple elements
    first = nested_list[0]
    rest = nested_list[1:]

    if isinstance(first, list):
        first_sum = sum_nested_actually_broken(first)
    else:
        first_sum = first

    rest_sum = sum_nested_actually_broken(rest)

    # BUG: What if first_sum or rest_sum is None?
    return first_sum + rest_sum

print("\nTesting actually broken function:")
test_input = [[]]
try:
    result = sum_nested_actually_broken(test_input)
    print(f"sum_nested({test_input}) = {result}")
except Exception as e:
    print(f"✗ Error: {type(e).__name__}: {e}")
    print("\nDebug trace:")
    sum_nested_debug(test_input)

Python Output:

Testing actually broken function:
sum_nested([[]]) = 0

Okay, that works too! Let me create a genuinely broken version:

def sum_nested_genuinely_broken(nested_list):
    """
    GENUINELY BROKEN: Returns None for empty nested lists.
    """
    if len(nested_list) == 0:
        return None  # ✗ BUG: Should return 0!

    first = nested_list[0]
    rest = nested_list[1:]

    if isinstance(first, list):
        first_sum = sum_nested_genuinely_broken(first)
    else:
        first_sum = first

    rest_sum = sum_nested_genuinely_broken(rest)

    # This will crash when first_sum or rest_sum is None
    return first_sum + rest_sum

print("\nTesting genuinely broken function:")
test_input = [[]]
try:
    result = sum_nested_genuinely_broken(test_input)
    print(f"sum_nested({test_input}) = {result}")
except Exception as e:
    print(f"✗ Error: {type(e).__name__}: {e}")
    print("\nApplying debugging workflow:")
    print("\nStep 1: Error message tells us:")
    print("  - TypeError: trying to add None to something")
    print("  - Happens when processing empty nested list")
    print("\nStep 2: Manual trace:")
    print("  sum_nested([[]])")
    print("    first=[], rest=[]")
    print("    first_sum = sum_nested([])")
    print("      len([]) == 0")
    print("      return None  ← BUG!")
    print("    rest_sum = sum_nested([])")
    print("      return None  ← BUG!")
    print("    return None + None  ← TypeError!")
    print("\nStep 3: Fix - change base case to return 0 instead of None")

Python Output:

Testing genuinely broken function:
✗ Error: TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

Applying debugging workflow:

Step 1: Error message tells us:
  - TypeError: trying to add None to something
  - Happens when processing empty nested list

Step 2: Manual trace:
  sum_nested([[]])
    first=[], rest=[]
    first_sum = sum_nested([])
      len([]) == 0
      return None  ← BUG!
    rest_sum = sum_nested([])
      return None  ← BUG!
    return None + None  ← TypeError!

Step 3: Fix - change base case to return 0 instead of None

The fix:

def sum_nested_fixed(nested_list):
    """
    FIXED: Returns 0 for empty lists.
    """
    if len(nested_list) == 0:
        return 0  # ✓ Fixed!

    first = nested_list[0]
    rest = nested_list[1:]

    if isinstance(first, list):
        first_sum = sum_nested_fixed(first)
    else:
        first_sum = first

    rest_sum = sum_nested_fixed(rest)

    return first_sum + rest_sum

print("\nTesting fixed function:")
for test_input in [[[]], [1, [2, 3], 4], []]:
    result = sum_nested_fixed(test_input)
    print(f"✓ sum_nested({test_input}) = {result}")

Python Output:

Testing fixed function:
✓ sum_nested([[]]) = 0
✓ sum_nested([1, [2, 3], 4]) = 10
✓ sum_nested([]) = 0

Key lesson: The debugging workflow helped us: 1. Identify the error type and location 2. Trace execution to find where None was introduced 3. Recognize the base case was returning the wrong value 4. Fix it by returning the correct identity value (0 for addition)

Practice: Fix Broken Recursive Functions

Hands-On Practice

Now it's your turn. Below are five broken recursive functions. For each one:

Run the code and observe the failure
Apply the debugging workflow
Identify the root cause
Fix the bug
Verify your fix works

Exercise 1: Broken Factorial

Problem: Calculate factorial of n (n! = n × (n-1) × ... × 1)

def factorial_broken(n):
    """
    BROKEN: Calculate factorial of n.
    Bug: Missing base case.
    """
    return n * factorial_broken(n - 1)

# Test it
print("Exercise 1: Broken Factorial")
try:
    result = factorial_broken(5)
    print(f"factorial(5) = {result}")
except RecursionError:
    print("✗ RecursionError: maximum recursion depth exceeded")
    print("\nYour task:")
    print("1. What base case is missing?")
    print("2. What should it return?")
    print("3. Fix the function")

Expected output:

Exercise 1: Broken Factorial
✗ RecursionError: maximum recursion depth exceeded

Your task:
1. What base case is missing?
2. What should it return?
3. Fix the function

Solution (try to solve it yourself first!):

def factorial_fixed(n):
    """
    FIXED: Calculate factorial of n.
    """
    # BASE CASE: 0! = 1, 1! = 1
    if n <= 1:
        return 1

    # RECURSIVE CASE
    return n * factorial_fixed(n - 1)

print("\nSolution:")
print(f"factorial(5) = {factorial_fixed(5)}")  # Should be 120
print(f"factorial(0) = {factorial_fixed(0)}")  # Should be 1

Exercise 2: Broken List Reversal

Problem: Reverse a list recursively

def reverse_broken(lst):
    """
    BROKEN: Reverse a list recursively.
    Bug: Base case returns wrong value.
    """
    if len(lst) == 0:
        return None  # ✗ BUG!

    if len(lst) == 1:
        return lst

    first = lst[0]
    rest = lst[1:]

    return reverse_broken(rest) + [first]

print("\nExercise 2: Broken List Reversal")
try:
    result = reverse_broken([1, 2, 3])
    print(f"reverse([1, 2, 3]) = {result}")
except TypeError as e:
    print(f"✗ TypeError: {e}")
    print("\nYour task:")
    print("1. What should the empty list base case return?")
    print("2. Why does returning None cause a TypeError?")
    print("3. Fix the function")

Solution:

def reverse_fixed(lst):
    """
    FIXED: Reverse a list recursively.
    """
    if len(lst) == 0:
        return []  # ✓ Fixed: return empty list, not None

    if len(lst) == 1:
        return lst

    first = lst[0]
    rest = lst[1:]

    return reverse_fixed(rest) + [first]

print("\nSolution:")
print(f"reverse([1, 2, 3]) = {reverse_fixed([1, 2, 3])}")  # [3, 2, 1]
print(f"reverse([]) = {reverse_fixed([])}")  # []

Exercise 3: Broken Binary Search

Problem: Search for target in sorted list

def binary_search_broken(lst, target, low, high):
    """
    BROKEN: Binary search in sorted list.
    Bug: Base case condition is wrong.
    """
    if low >= high:  # ✗ BUG!
        return -1

    mid = (low + high) // 2

    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search_broken(lst, target, mid + 1, high)
    else:
        return binary_search_broken(lst, target, low, mid - 1)

print("\nExercise 3: Broken Binary Search")
lst = [1, 3, 5, 7, 9, 11, 13]
result = binary_search_broken(lst, 7, 0, len(lst) - 1)
print(f"binary_search([1,3,5,7,9,11,13], 7) = {result}")
print(f"Expected: 3 (index of 7)")
print("\nYour task:")
print("1. Why does low >= high fail to find the target?")
print("2. What should the base case condition be?")
print("3. Fix the function")

Solution:

def binary_search_fixed(lst, target, low, high):
    """
    FIXED: Binary search in sorted list.
    """
    if low > high:  # ✓ Fixed: use > instead of >=
        return -1

    mid = (low + high) // 2

    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return binary_search_fixed(lst, target, mid + 1, high)
    else:
        return binary_search_fixed(lst, target, low, mid - 1)

print("\nSolution:")
lst = [1, 3, 5, 7, 9, 11, 13]
print(f"binary_search([1,3,5,7,9,11,13], 7) = {binary_search_fixed(lst, 7, 0, len(lst) - 1)}")
print(f"binary_search([1,3,5,7,9,11,13], 2) = {binary_search_fixed(lst, 2, 0, len(lst) - 1)}")

Exercise 4: Broken Tree Height

Problem: Calculate height of binary tree

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def tree_height_broken(node):
    """
    BROKEN: Calculate height of binary tree.
    Bug: Doesn't handle None nodes.
    """
    # Missing base case for None!

    left_height = tree_height_broken(node.left)
    right_height = tree_height_broken(node.right)

    return 1 + max(left_height, right_height)

print("\nExercise 4: Broken Tree Height")
# Create tree:
#       1
#      / \
#     2   3
#    /
#   4
tree = TreeNode(1,
    TreeNode(2, TreeNode(4)),
    TreeNode(3)
)

try:
    result = tree_height_broken(tree)
    print(f"tree_height(tree) = {result}")
except AttributeError as e:
    print(f"✗ AttributeError: {e}")
    print("\nYour task:")
    print("1. What happens when node is None?")
    print("2. What should the base case return for None?")
    print("3. Fix the function")

Solution:

def tree_height_fixed(node):
    """
    FIXED: Calculate height of binary tree.
    """
    # BASE CASE: None node has height 0
    if node is None:
        return 0

    left_height = tree_height_fixed(node.left)
    right_height = tree_height_fixed(node.right)

    return 1 + max(left_height, right_height)

print("\nSolution:")
print(f"tree_height(tree) = {tree_height_fixed(tree)}")  # Should be 3
print(f"tree_height(None) = {tree_height_fixed(None)}")  # Should be 0

Exercise 5: Broken Palindrome Checker

Problem: Check if string is palindrome recursively

def is_palindrome_broken(s):
    """
    BROKEN: Check if string is palindrome.
    Bug: Base case doesn't handle all cases.
    """
    # BASE CASE: Empty string
    if len(s) == 0:
        return True

    # Check first and last characters
    if s[0] != s[-1]:
        return False

    # RECURSIVE CASE: Check middle
    return is_palindrome_broken(s[1:-1])

print("\nExercise 5: Broken Palindrome Checker")
test_cases = [
    ("racecar", True),
    ("hello", False),
    ("a", True),
    ("", True),
]

for test_input, expected in test_cases:
    result = is_palindrome_broken(test_input)
    status = "✓" if result == expected else "✗"
    print(f"{status} is_palindrome('{test_input}') = {result} (expected {expected})")

print("\nYour task:")
print("1. Which test case fails?")
print("2. What base case is missing?")
print("3. Fix the function")

Solution:

def is_palindrome_fixed(s):
    """
    FIXED: Check if string is palindrome.
    """
    # BASE CASE: Empty string or single character
    if len(s) <= 1:  # ✓ Fixed: handle both empty and single char
        return True

    # Check first and last characters
    if s[0] != s[-1]:
        return False

    # RECURSIVE CASE: Check middle
    return is_palindrome_fixed(s[1:-1])

print("\nSolution:")
for test_input, expected in test_cases:
    result = is_palindrome_fixed(test_input)
    status = "✓" if result == expected else "✗"
    print(f"{status} is_palindrome('{test_input}') = {result} (expected {expected})")

Summary of Fixes

Exercise	Bug Type	Root Cause	Fix
1. Factorial	Missing base case	No termination condition	Add `if n <= 1: return 1`
2. List Reversal	Wrong base case value	Returns None instead of []	Change `return None` to `return []`
3. Binary Search	Wrong base case condition	Uses >= instead of >	Change `if low >= high` to `if low > high`
4. Tree Height	Missing base case	Doesn't handle None nodes	Add `if node is None: return 0`
5. Palindrome	Incomplete base case	Doesn't handle single char	Change `len(s) == 0` to `len(s) <= 1`

Key Patterns: - Missing base case → Add explicit check at function start - Wrong base case value → Verify return value matches problem semantics - Wrong base case condition → Test boundary conditions carefully - Incomplete base cases → List all edge cases before coding

The Journey: From Problem to Solution

Synthesis: What We've Learned

Let's trace the complete journey of our directory size calculator, from naive implementation to production-ready code.

The Evolution

Iteration	Problem	Technique Applied	Result	Complexity Impact
0	Works for simple cases	None	Baseline implementation	O(n) time, O(d) space
1	Crashes on permission errors	Error handling	Graceful failure	Same complexity
2	Implicit base case unclear	Explicit base case	Clearer code	Same complexity
3	Infinite loop on circular symlinks	Visited tracking	Handles circular refs	O(n) time, O(d) space + visited set
Final	Symlink handling ambiguous	Configuration parameter	Flexible behavior	Same complexity

Where: - n = total number of files and directories - d = maximum directory depth

Final Implementation

Here's our complete, production-ready directory size calculator:

def calculate_directory_size(path, visited=None, follow_symlinks=False):
    """
    Calculate total size of directory in bytes.

    Handles:
    - Permission errors (skips inaccessible directories)
    - Circular symlinks (tracks visited directories)
    - Broken symlinks (skips invalid paths)
    - Empty directories (returns 0)
    - Configurable symlink behavior

    Args:
        path: Directory path to analyze
        visited: Set of visited paths (for circular reference detection)
        follow_symlinks: If True, count target size; if False, count symlink size

    Returns:
        Total size in bytes

    Time Complexity: O(n) where n = total files + directories
    Space Complexity: O(d) where d = max directory depth
    """
    # Initialize visited set on first call
    if visited is None:
        visited = set()

    # BASE CASE 1: Resolve symlinks to real path
    try:
        real_path = os.path.realpath(path)
    except (OSError, ValueError):
        # Broken symlink or invalid path
        return 0

    # BASE CASE 2: Already visited (circular reference)
    if real_path in visited:
        return 0

    # Mark as visited
    visited.add(real_path)

    # BASE CASE 3: Permission denied
    try:
        items = os.listdir(real_path)
    except PermissionError:
        return 0

    # BASE CASE 4: Empty directory
    if not items:
        return 0

    # RECURSIVE CASE: Process all items
    total_size = 0
    for item in items:
        item_path = os.path.join(real_path, item)

        if os.path.isdir(item_path):
            # Recurse into subdirectory
            total_size += calculate_directory_size(item_path, visited, follow_symlinks)
        else:
            # Add file size
            try:
                if follow_symlinks:
                    total_size += os.path.getsize(item_path)
                else:
                    total_size += os.lstat(item_path).st_size
            except (PermissionError, FileNotFoundError):
                pass

    return total_size

# Comprehensive test
test_dir = create_test_directory()

# Add various edge cases
file_path = os.path.join(test_dir, "file1.txt")
symlink_to_file = os.path.join(test_dir, "link_to_file")
os.symlink(file_path, symlink_to_file)

subdir_path = os.path.join(test_dir, "subdir")
symlink_to_dir = os.path.join(subdir_path, "link_to_parent")
os.symlink(test_dir, symlink_to_dir)

print("Final Implementation Test")
print("=" * 60)
print(f"Directory: {test_dir}")
print()

size_follow = calculate_directory_size(test_dir, follow_symlinks=True)
print(f"Size (follow symlinks):     {size_follow} bytes")

size_no_follow = calculate_directory_size(test_dir, follow_symlinks=False)
print(f"Size (don't follow):        {size_no_follow} bytes")

print()
print("✓ Handles all edge cases:")
print("  - Permission errors")
print("  - Circular symlinks")
print("  - Empty directories")
print("  - Broken symlinks")
print("  - Configurable symlink behavior")

shutil.rmtree(test_dir)

Decision Framework: Which Approach When?

When designing recursive functions, consider:

1. Base Case Strategy

Approach	When to Use	Example
Implicit (loop handles empty)	Simple list processing	`for item in items: ...`
Explicit (check upfront)	Multiple base cases	`if not items: return 0`
Multiple explicit	Complex termination	Our directory size function

2. Decomposition Strategy

Pattern	Best For	Trade-offs
First + Rest	Teaching, natural list processing	Creates intermediate lists
Flatten Then Process	When flat structure is useful	Two-pass algorithm
Accumulator	Space-critical applications	Less intuitive
Divide and Conquer	Halving problems	Requires merge step

3. Error Handling Strategy

Approach	When to Use	Example
Return sentinel value	Errors are expected	`return 0` for permission denied
Raise exception	Errors are exceptional	`raise ValueError` for invalid input
Try-except wrapper	External failures	`try: os.listdir()`

Complexity Analysis

Time Complexity: O(n) - Each file and directory visited exactly once - Constant work per item - Visited set lookup is O(1) average case

Space Complexity: O(d) - Call stack depth: d (max directory depth) - Visited set: O(d) (number of unique directories) - Total: O(d)

Recurrence Relation:

T(n) = T(n₁) + T(n₂) + ... + T(nₖ) + O(1)

Where n₁, n₂, ..., nₖ are sizes of subdirectories.

This solves to O(n) because each item is processed once.

Lessons Learned

1. Base cases are not optional - Every recursive function needs at least one - Missing base cases cause infinite recursion - Wrong base case values cause incorrect results

2. Multiple base cases are common - Real-world problems have multiple termination conditions - Order matters when base cases overlap - Test each base case independently

3. Decomposition choices matter - Different decompositions lead to different base cases - Choose decomposition that makes base cases obvious - Consider both clarity and efficiency

4. Error handling is part of base case design - Environmental failures need base cases too - Decide: return sentinel value or raise exception - Document error handling behavior

5. Debugging is systematic - Read error messages carefully - Trace call stack manually - Verify base cases in isolation - Check progress toward base case - Test edge cases explicitly

6. Production code needs robustness - Handle all edge cases - Add configuration parameters for flexibility - Document assumptions and limitations - Include complexity analysis